package com.demo.java.OD501_550.OD509;

import java.util.Scanner;

/**
 * @author bug菌
 * @Source 公众号：猿圈奇妙屋
 * @des： 【编码能力提升计划(B卷-100分)】问题
 * @url： https://blog.csdn.net/weixin_43970743/article/details/146478651
 */
public class OdMain {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);
        // 读取题目时间列表和最大天数
        String input_str = in.nextLine();
        String[] tmp2 = input_str.split(",");
        int[] nums = new int[tmp2.length];
        for (int i = 0; i < tmp2.length; i++) {
            nums[i] = Integer.parseInt(tmp2[i]);  // 题目的所需时间
        }
        int m = Integer.parseInt(in.nextLine());  // 可用的最大天数

        // 调用二分查找函数
        System.out.println(minTime(nums, m));
    }

    // 二分查找找到最小时间限制
    public static int minTime(int[] time, int m) {
        int left = 0;
        int right = Integer.MAX_VALUE;

        // 二分查找时间限制
        while (left <= right) {
            int mid = left + (right - left) / 2;

            // 如果当前时间限制可以在m天内完成所有题目
            if (check(time, mid, m)) {
                // 缩小查找范围
                right = mid - 1;
            } else {
                // 否则扩大查找范围
                left = mid + 1;
            }
        }
        return left;  // 最小的时间限制
    }

    // 检查是否能在给定时间限制内完成题目
    public static boolean check(int[] time, int target, int m) {
        int maxTime = 0;
        int total = 0;
        int days = 1;  // 初始时为第一天
        boolean helper = true;  // 是否使用了场外帮助

        // 遍历每个题目
        for (int i = 0; i < time.length; i++) {
            // 更新当天做题时间
            maxTime = Math.max(maxTime, time[i]);
            total += time[i];

            // 如果当天时间超出限制
            if (total > target) {
                // 如果没有使用场外帮助
                if (helper) {
                    // 使用场外帮助，减去当前做题时间最长的题目
                    total -= maxTime;
                    helper = false;  // 标记已使用过场外帮助
                } else {
                    // 超过时间并且已使用过场外帮助，得重新开始新的一天
                    days++;
                    helper = true;  // 重置场外帮助标记
                    maxTime = 0;  // 重置当天最大题目时间
                    total = 0;  // 重置当天总时间
                    i--;  // 将当前题目移到新的一天
                }
            }
        }
        // 如果最终天数不超过最大天数m，则返回true
        return m >= days;
    }
}